/*
 * ver: 0.1, date 03-01-2008 by Marcel Hekman
 * Implemented Dijkstra solve with breadth first graph build (not working).
 * ver: 0.2, date 03-01-2008 by Marcel Hekman
 * Implemented depth first graph build (works)
 * Some other bugfixes.
 * ver: 0.3, date 04-01-2008 by Marcel Hekman
 * Made the solving process more clear in te mazegraph.
 * Cleaned up breadth first graph build.
 * ver: 0.4, date 04-01-2008 by Marcel Hekman
 * - Started moving GraphBuilding to the tick() function.
 * ver: 0.5, date 05-01-2008 by Marcel Hekman
 * - All known bugs solved.
 * ver: 0.6, date 06-01-2008 by Marcel Hekman
 * - Graph building weer breadth first gemaakt (handiger met tick() en geen stackoverflows meer)
 * - Graph building tick compatible gemaakt
 * - HighLight ook tick compatible gemaakt.
 */

package mazeAssignment.solve;


import mazeAssignment.*;
import mazeAssignment.datastructures.Edge;
import mazeAssignment.datastructures.Path;
import mazeAssignment.datastructures.Vertex;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Requires more calculation power then the breadth first search.
 * Because it always scans the entire maze.
 * @author jeroen, jeroen, marcel en teun
 */
public class DijkstraShortestSolve implements Solve
{
	private static enum Direction { NORTH, EAST, SOUTH, WEST };
	
	private Maze maze;
	private Queue<Vertex> graphBuildQueue;
	private Map<Integer,Vertex> vertexMap;
	private PriorityQueue<Path> pathQueue;

	private Vertex firstVertex;
	private Vertex vertexToHighLight;
	
	private boolean needGraphBuilding;
	private boolean needSolving;
	private boolean needHighLighting;
	private boolean isFinished;
	
	public DijkstraShortestSolve()
	{
		this.maze = null;
		this.graphBuildQueue = null;
		this.vertexMap = null;
		this.pathQueue = null;
		this.firstVertex = null;
		this.vertexToHighLight = null;
		
		this.needGraphBuilding = true;
		this.needSolving = true;
		this.needHighLighting = true;
		this.isFinished = false;
	}
	
	
	@Override
	public void initialise(Maze m) throws SolveException
	{
		this.maze = m;
		this.graphBuildQueue = new LinkedList<Vertex>();
		this.vertexMap = new HashMap<Integer,Vertex>();
		this.pathQueue = new PriorityQueue<Path>();
		
		this.needGraphBuilding = true;
		this.needSolving = true;
		this.needHighLighting = true;
		this.isFinished = false;
		
		this.vertexToHighLight = null;
		this.firstVertex = findStart();
		this.firstVertex.weight = 0;
		
		//For the build graph phase.
		this.graphBuildQueue.add(firstVertex);
		vertexMap.put(firstVertex.number, firstVertex);		//Add the first vertex to the map
	}
	
	@Override
	public boolean isDone()
	{
		return isFinished;
	}
	

	/**
	 * Find the start position anywhere in the maze.
	 * Place the start item in the vertex map and
	 * enqueue the start item.
	 * @return The vertex of the start position.
	 */
	private Vertex findStart() throws SolveException
	{
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		
		for(int x = 0; x < xSize; x++)
		{
			for(int y = 0; y < ySize; y++)
			{
				if(maze.getSolveState(x, y) == Maze.SOLVE_START)
				{
					int vertexNumber = x + (y * xSize);
					Vertex startVertex = new Vertex(vertexNumber);
					
					return startVertex;
				}
			}
		}
		
		throw new SolveException("DijkstraShortestSolve.findStart(): Unable to find maze start.");
	}

	/**
	 * Calls the underlying function depending on which phase we are currently in.
	 */
	@Override
	public void tick() throws SolveException
	{
		if(isFinished)
			throw new SolveException("DijkstraShortestSolve.tick(): Already solved.");
		
		//Graph building
		if(needGraphBuilding)
		{
			graphBuildTick();
		}
		//Solving
		else if(needSolving)
		{
			solveTick();
		}
		//Valid path highlighting
		else if(needHighLighting)
		{
			highLightTick();
		}
		//Done
		else
		{
			isFinished = true;
		}
	}
	

	/**
	 * Executes one step of the graph build algorithm.
	 * This algorithm uses breadth first search.
	 * Breadth-first is easier to make tick-compatible.
	 * @throws SolveException When called when already finished or other errors.
	 */
	private void graphBuildTick() throws SolveException
	{
		if(graphBuildQueue.isEmpty())
			throw new SolveException("DijkstraShortestSolve.graphBuildTick(): Graph already build.");
		
		
		Vertex currentVertex = graphBuildQueue.poll();
		
		//Decode vertex number to x and y
		int xSize = maze.getSizeX();
		int x = currentVertex.number % xSize;
		int y = currentVertex.number / xSize;
		
		//Check the tunnels for the first node
		checkAllDirections(x, y, currentVertex, null, 1);
		
		
		//Signal that we are finished
		if(graphBuildQueue.isEmpty())
		{
			this.needGraphBuilding = false;
			
			//Wipe clean all the graph building colors.
			maze.clearSolveState();
			
			//For the solve phase.
			this.pathQueue.add( new Path(firstVertex, 0));
		}
	}
	
	/**
	 * Executes the Dijkstra algorithm to determine the shortest path.
	 * @throws SolveException When unable to find an exit.
	 */
	private void solveTick() throws SolveException
	{
		if(pathQueue.isEmpty())
			throw new SolveException("DijkstraShortestSolve.solveTick(): Empty path queue.");
		
		int mazeWidth = maze.getSizeX();
		
		
		Path currentPath = pathQueue.poll();
		Vertex currentVertex = currentPath.dest;
		
		int xPosition = currentVertex.number % mazeWidth;
		int yPosition = currentVertex.number / mazeWidth;
		
		//Check if we are at the end
		if(maze.getSolveState(xPosition, yPosition) == Maze.SOLVE_END)
		{
			//Signal that we are finished
			this.needSolving = false;
			
			//Save the vertex 
			this.vertexToHighLight = currentVertex;
			return;
		}
		
		//By default mark everything as invalid so
		//it is easier to mark the valid path in the end.
		maze.markAsInvalid(xPosition, yPosition);
		
		for(Edge e : currentVertex.edges)
		{
			Vertex connectedVertex = e.dest;
			
			if(connectedVertex.weight > currentVertex.weight + e.weight)
			{
				connectedVertex.weight = currentVertex.weight + e.weight;
				connectedVertex.prev = currentVertex;
				pathQueue.add( new Path(connectedVertex, connectedVertex.weight) );
			}
		}
		
		if(pathQueue.isEmpty())
			throw new SolveException("DijkstraShortestSolve.solveTick(): No exit defined.");
	}
	
	/**
	 * Executes an algorithm to paint the shortest path.
	 * It follows the Vertex.prev data member so it will draw the path backwards.
	 * @throws SolveException When unable to find an exit.
	 */
	private void highLightTick()
	{
		//Calculate the shortest distance by checking all edges.
		int maxDepth = Integer.MAX_VALUE;
		for(Edge e : this.vertexToHighLight.edges)
		{
			if(e.dest == this.vertexToHighLight.prev && e.weight < maxDepth)
			{
				maxDepth = (int)e.weight;
			}
		}
		
		int width = maze.getSizeX();
		int x = this.vertexToHighLight.number % width;
		int y = this.vertexToHighLight.number / width;
		
		if(directionIsAccessible(x, y, Direction.NORTH))
			highLightPathIfValid(x, y-1, Direction.SOUTH, this.vertexToHighLight.prev, maxDepth);
		
		if(directionIsAccessible(x, y, Direction.EAST))
			highLightPathIfValid(x+1, y, Direction.WEST, this.vertexToHighLight.prev, maxDepth);
		
		if(directionIsAccessible(x, y, Direction.SOUTH))
			highLightPathIfValid(x, y+1, Direction.NORTH, this.vertexToHighLight.prev, maxDepth);
		
		if(directionIsAccessible(x, y, Direction.WEST))
			highLightPathIfValid(x-1, y, Direction.EAST, this.vertexToHighLight.prev, maxDepth);
		
		maze.visit(x, y);
		this.vertexToHighLight = this.vertexToHighLight.prev;
		
		//If weight == 0 we re back at the beginning.
		if(this.vertexToHighLight.weight == 0)
		{
			this.vertexToHighLight = this.vertexToHighLight.prev;
			this.needHighLighting = false;
		}
	}
	
	/**
	 * Check all direction 
	 * @param x Coordinate.
	 * @param y Coordinate.
	 * @param previous Previous vertex, used to setup edges in a different function.
	 * @param origin The direction which should be skipped (ignored if null).
	 * @param weight Current weight of the path.
	 */
	private void checkAllDirections(int x, int y, Vertex previous, Direction origin, int weight)
	{
		if((origin == null || Direction.NORTH != origin) &&
		directionIsAccessible(x, y, Direction.NORTH))
		{
			findNewNode(x, y-1, Direction.SOUTH, previous, weight);
		}
		if((origin == null || Direction.EAST != origin) &&
		directionIsAccessible(x, y, Direction.EAST))
		{
			findNewNode(x+1, y, Direction.WEST, previous, weight);
		}
		if((origin == null || Direction.SOUTH != origin) &&
		directionIsAccessible(x, y, Direction.SOUTH))
		{
			findNewNode(x, y+1, Direction.NORTH, previous, weight);
		}
		if((origin == null || Direction.WEST != origin) &&
		directionIsAccessible(x, y, Direction.WEST))
		{
			findNewNode(x-1, y, Direction.EAST, previous, weight);
		}
	}
	
	/**
	 * Used to find a new node. Is used to skip parts that only have to accessible directions.
	 * And only considers 'intersections' and SOLVE_END as nodes.
	 * @param x Coordinate.
	 * @param y Coordinate.
	 * @param origin The direction which should be skipped, because we came from this direction.
	 * @param previous The previous vertex used to set up edges.
	 * @param weight The weight of the path.
	 */
	private void findNewNode(int x, int y, Direction origin, Vertex previous, int weight)
	{
		int walls = countWalls(x, y);
		
		//A new weighted node
		if(walls < 2 || maze.getSolveState(x, y) == Maze.SOLVE_END)
		{
			maze.markAsInvalid(x, y);
			processNode(x, y, previous, origin, weight);
		}
		//2 nodes, find the end we didn't come from
		else if(walls == 2)
		{
			checkAllDirections(x, y, previous, origin, weight+1);
		}
	}
	
	/**
	 * Used to generate a new vertex at the current location and setup edges between vertexes.
	 * And add the vertex to the Queue.
	 * @param x Coordinate.
	 * @param y Coordinate.
	 * @param previous Previous vertex used to setup edges.
	 * @param origin The direction we came from, so we don't keep going in circles.
	 * @param pathWeight The weight of the current path.
	 */
	private void processNode(int x, int y, Vertex previous, Direction origin, int pathWeight)
	{
		int vertexNumber = x + (y * maze.getSizeX());
		Vertex current;
		
		//Vertex already present in the vertex map, check edges.
		if(vertexMap.containsKey(vertexNumber))
		{
			current = vertexMap.get(vertexNumber);
			
			//Check every edge if it is already connected to this one
			for(Edge e : current.edges)
			{
				if(e.dest == previous)
				{
					//No need to add edges or to further examine the node.
					return;
				}
			}
			
			//Add the missing edges
			current.edges.add(new Edge(previous, pathWeight));
			previous.edges.add(new Edge(current, pathWeight));
			
			//No need to further examine the node.
			return;
		}
		//A new vertex, add it and setup edges.
		else
		{
			current = new Vertex(vertexNumber);
			vertexMap.put(vertexNumber, current);
			
			current.edges.add(new Edge(previous, pathWeight));
			previous.edges.add(new Edge(current, pathWeight));
			
			//Add it to the graph build queue.
			this.graphBuildQueue.add( current );
		}
	}
	
	/**
	 * Returns true if a direction is accessible (not outside the maze and no wall).
	 * @param x Coordinate of the current location.
	 * @param y Coordinate of the current location.
	 * @param d Direction to check.
	 * @return True if a direction is accessible.
	 */
	private boolean directionIsAccessible(int x, int y, Direction d)
	{
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		if(d == Direction.NORTH && y > 0 && ! maze.getNorth(x, y))
			return true;
		else if(d == Direction.EAST && x < (xSize-1) && ! maze.getEast(x, y))
			return true;
		else if(d == Direction.SOUTH && y < (ySize-1) && ! maze.getSouth(x, y))
			return true;
		else if(d == Direction.WEST && x > 0 && ! maze.getWest(x, y))
			return true;
		
		return false;
	}
	
	/**
	 * Count the surrounding walls.
	 * @param element
	 * @return The number of walls.
	 */
	private int countWalls(int x, int y)
	{
		int walls = 0;
		
		if(maze.getNorth(x, y))
			walls++;
		
		if(maze.getEast(x, y))
			walls++;
		
		if(maze.getSouth(x, y))
			walls++;
		
		if(maze.getWest(x, y))
			walls++;
		
		return walls;
	}
	
	/**
	 * Find the end of the path and paints it if it's the one we're looking for.
	 * @param current
	 */
	private boolean highLightPathIfValid(int x, int y, Direction origin, Vertex target, int maxDepth)
	{
		if(maxDepth < 1)
		{
			return false;
		}
		
		//Found a node
		if(countWalls(x, y) < 2 || maze.getSolveState(x, y) == Maze.SOLVE_START)
		{
			int vertexNumber = x + (y * maze.getSizeX());
			Vertex found = vertexMap.get(vertexNumber);
			
			if(found == target)
			{
				maze.visit(x, y);
				return true;
			}
			else
				return false;
		}
		
		//Keep searching for a node
		boolean paint = false;
		if(origin != Direction.NORTH && directionIsAccessible(x, y, Direction.NORTH))
			paint = highLightPathIfValid(x, y-1, Direction.SOUTH, target, maxDepth-1);
		
		else if(origin != Direction.EAST && directionIsAccessible(x, y, Direction.EAST))
			paint = highLightPathIfValid(x+1, y, Direction.WEST, target, maxDepth-1);
		
		else if(origin != Direction.SOUTH && directionIsAccessible(x, y, Direction.SOUTH))
			paint = highLightPathIfValid(x, y+1, Direction.NORTH, target, maxDepth-1);
		
		else if(origin != Direction.WEST && directionIsAccessible(x, y, Direction.WEST))
			paint = highLightPathIfValid(x-1, y, Direction.EAST, target, maxDepth-1);
		
		//Paint the element if it's the right path.
		if(paint)
		{
			maze.visit(x, y);
			return true;
		}
			
		
		//Dead end
		return false;
	}
}
